Search for: All records

Cellulose, the most abundant polysaccharide on earth composing plant cell walls, is synthesized by coordinated action of multiple enzymes in cellulose synthase complexes embedded within the plasma membrane. Multiple chains of cellulose fibrils form intertwined extracellular matrix networks. It remains largely unknown how newly synthesized cellulose is assembled into an intricate fibril network on cell surfaces. Here, we have established an in vivo time-resolved imaging platform to continuously visualize cellulose biosynthesis and fibril network assembly onArabidopsis thalianaprotoplast surfaces as the primary cell wall regenerates. Our observations provide the basis for a model of cellulose fibril network development in protoplasts driven by an interplay of multiscale dynamics that includes rapid diffusion and coalescence of nascent cellulose fibrils, processive elongation of single fibrils, and cellulose fibrillar network rearrangement during maturation. This study provides fresh insights into the dynamic and mechanistic aspects of cell wall synthesis at the single-cell level. 

We present algorithms of two flavors—one rooted in constraint satisfaction problems (CSPs) and the other in learning dynamics—to compute pure-strategy Nash equilibrium (PSNE) in k-dimensional congestion games (k-DCGs) and their variants. The two algorithmic approaches are driven by whether or not a PSNE is guaranteed to exist. We first show that deciding the existence of a PSNE in a k-DCG is NP-complete even when players have binary and unit demand vectors. For general cost functions (potentially non-monotonic), we devise a new CSP-inspired algorithmic framework for PSNE computation, leading to algorithms that run in polynomial time under certain assumptions while offering exponential savings over standard CSP algorithms. We further refine these algorithms for variants of k-DCGs. Our experiments demonstrate the effectiveness of this new CSP framework for hard, non-monotonic k-DCGs. We then provide learning dynamics-based PSNE computation algorithms for linear and exponential cost functions. These algorithms run in polynomial time under certain assumptions. For general cost, we give a learning dynamics algorithm for an (α, β)-approximate PSNE (for certain α and β). Lastly, we also devise polynomial-time algorithms for structured demands and cost functions. 

We study pure-strategy Nash equilibrium (PSNE) computation in 𝑘-dimensional congestion games (𝑘-DCGs) where the weights or demands of the players are 𝑘-dimensional vectors. We first show that deciding the existence of a PSNE in a 𝑘-DCG is NP-complete even for games when players have binary and unit demand vectors. We then focus on computing PSNE for 𝑘-DCGs and their variants with general, linear, and exponential cost functions. For general cost functions (potentially non-monotonic), we provide the first configuration-space framework to find a PSNE if one exists. For linear and exponential cost functions, we provide potential function-based algorithms to find a PSNE. These algorithms run in polynomial time under certain assumptions. We also study structured demands and cost functions, giving polynomial-time algorithms to compute PSNE for several cases. For general cost functions, we give a constructive proof of existence for an (𝛼, 𝛽)-PSNE (for certain 𝛼 and 𝛽), where 𝛼 and 𝛽 are multiplicative and additive approximation factors, respectively. 

Although predictive AI models have grown to dominate computational finance, they are often limited in their applications when it comes to studying interventions and explaining behavioral outcomes. Financial economics, on the other hand, has a rich history of analytical approaches to asset-pricing theory, often requiring sweeping assumptions. In this paper, we construct an agent-based model of asset markets that is able to dispense with onerous restrictions on agent behaviors and beliefs, while having analytical validity and providing insights into the functioning of asset markets. In particular, we evaluate our models with respect to several traditional financial economic theories like Tobin’s separation theorem and the capital asset pricing model (CAPM). We devise a network representing trades to show the emergence of different roles played by the agents. We study interventions, such as shocks, and explain the outcomes using our model. Finally, we investigate the effects of noise trading and show that noisy agents converge to different equilibrium points due to their differences in beliefs. Put together, this paper presents an agent-based model that can be used to study the effects of heterogeneous beliefs and risks of the agents and shocks to assets at a systemic level, thereby connecting localized agent and asset characteristics to global or collective outcomes. 

Influence maximization (IM) has now been a widely studied topic, but only in recent years have studies considered overexposure. Overexposure is usually measured as the negative cost associated with reaching unintended recipients during an information cascade. A polynomial-time algorithm is known for cascades with overexposure when we can seed as many nodes as we want. This paper focuses on overexposure for the budgeted case of seeding, which has received little to no attention. We show that the problem is NP-hard even for restricted cases. For various special cases, we devise provable approximation algorithms, dynamic programming solutions, linear programming solutions, and heuristics. For the general case, we provide a linear programming solution and several fast and effective heuristics, mostly of the greedy flavor. We perform an extensive experimental study using synthetic and real-world networks. We investigate how network properties and model parameters impact our algorithms. It brings out interesting findings like why a low-quality product needs a smarter algorithm, and why certain algorithms do well on some networks but not others. 

Abstract Game-theoretic models of influence in networks often assume the network structure to be static. In this paper, we allow the network structure to vary according to the underlying behavioral context. This leads to several interesting questions on two fronts. First, how do we identify different contexts and learn the corresponding network structures using real-world data? We focus on the U.S. Senate and apply unsupervised machine learning techniques, such as fuzzy clustering algorithms and generative models, to identify spheres of legislation as context and learn an influence network for each sphere. Second, how do we analyze these networks to gain an insight into the role played by the spheres of legislation in various interesting constructs like polarization and most influential nodes? To this end, we apply both game-theoretic and social network analysis techniques. In particular, we show that game-theoretic notion of most influential nodes brings out the strategic aspects of interactions like bipartisan grouping, which structural centrality measures fail to capture. 

We propose a game-theoretic approach to generalizing the classical Schelling model. At the core of our model are two features that did not receive much attention before. First, we allow multiple individuals to occupy the same location. Second, each individual’s choice of location is influenced by their social network neighbors that also choose the same location. In addition, an individual’s choice is influenced by others in the adjacent locations in a network-structured way, which captures the main spirit of the classical Schelling model and its numerous extensions. Our solution concept is a stable configuration represented as a pure-strategy Nash equilibrium (PSNE). We show that even for various special cases of the problem, computing or counting PSNE is provably hard. We give algorithms for computing PSNE, including efficient algorithms for several special cases. We highlight some of the attractive features of our model, such as predicting very few PSNE, through experiments. 

Game-theoretic models of influence in networks often assume the network structure to be static. In this paper, we allow the network structure to vary according to the underlying behavioral context. This leads to several interesting questions on two fronts. First, how do we identify different contexts and learn the corresponding network structures using real-world data? We focus on the U.S. Senate and apply unsupervised machine learning techniques, such as fuzzy clustering algorithms and generative models, to identify different spheres of legislation as context and learn an influence network for each sphere. Second, how do we analyze these networks in order to gain an insight into the role played by the spheres of legislation in various interesting constructs like polarization and most influential nodes? To this end, we apply both game-theoretic and social network analysis techniques. In particular, we show that game-theoretic notion of most influential nodes brings out the strategic aspects of interactions like bipartisan grouping, which typical centrality measures fail to capture. We also show that for the same set of senators, some spheres of legislation are more polarizing than others.